/** Copyright 2012 Awen Limbourg */
#ifndef INDEX_TRIINDEX_H_
#define INDEX_TRIINDEX_H_


/**
 * @brief The TriIndex class, this is the main container/accessor of a trigram index of docs
 * sample:
 *   TriIndex test;
 *   IndexBuilder ib(&test);
 *   test.init();
 *   const char path[]="C:\\Dev\\Adobe\\4.6.0-Air3.2RC\\frameworks\\javascript\\fabridge\\samples\\fabridge\\javascript\\FABridge.js";
 *   ib.clearTriBits();
 *   ib.indexBuffer(path);
 *   ib.indexFile(path);
 *   test.insertTrigrams(0, ib.triBits);
 *   std::vector<size_t> hits;
 *   test.FindDocuments("input", &hits);
 */
class TriIndex
{
public:
    // ="abcdefghijklmnopqrstuvwxyz""0123456789""#/*-+=&/!_()[]{}\"'.,:$%";
    static const char _validChars[64];
    static int _hash64(char c)
    {
        c = tolower(c);
        const char* ptr = strrchr(_validChars, c);
        if (ptr == NULL)
            return 0;
        return (ptr - _validChars)+1;
    }
protected:
    std::vector<std::pair<size_t, std::string> >    _docArray;
    std::vector<std::string>                        _dirArray;
    // 64*64*64 = 262144 (or 32 kbytes of bit array),
    // better than std::vector<std::vector<size_t>> _masterTrigrams or
    // std::vector<size_t> _masterTrigrams[64*64*64]
    typedef SimpleArray<uint32_t, 64>               uint32_array;
    SimpleArray<uint32_array, 1>                    _masterTrigrams;
public:
    TriIndex() {}
    ~TriIndex() { shutdown(); }

    void   init();
    void   shutdown();

    // insert current buffer into master tirgram
    void insertTrigrams(size_t docId, unsigned char * const triBits)
    {
        for (size_t i = 0; i < (64*64*64); i++)
        {
            if ((triBits[i>>3] & (1<<(i & 7))) != 0 )
                _masterTrigrams[i].pushBack(docId);
        }
    }

    size_t addDirectory(const char* dir)
    {
        int index = _dirArray.size();
        _dirArray.push_back(std::string(dir));
        return index;
    }

    size_t addDocument(size_t dirId, const char* fname)
    {
        int index = _docArray.size();
        _docArray.push_back(std::pair<size_t,
                            std::string>(dirId, std::string(fname)));
        return index;
    }
    /**
     * @brief mergeWith (untested atm)
     * @param other
     */
    void mergeWith(const TriIndex* other)
    {
        size_t dirOffset = _dirArray.size();
        _dirArray.insert(_dirArray.end(), other->_dirArray.begin(), other->_dirArray.end());
        size_t docOffset = _docArray.size();
        _docArray.insert(_docArray.end(), other->_docArray.begin(), other->_docArray.end());
        for (size_t i=docOffset; i<_docArray.size(); i++)
            _docArray[i].first += dirOffset;
        for (size_t i=0; i<_masterTrigrams.size(); i++)
        {
            const uint32_array& _other = other->_masterTrigrams[i];
            if (_other.size()==0)
                continue;
            uint32_array& _current = _masterTrigrams[i];
            size_t triOffset = _current.size();//append(dirOffset);
            _current.resize(_current.size() + _other.size());
            memcpy(_current.begin()+triOffset, _other.begin(), _other.memSize());
            for (size_t tri=triOffset; tri<_current.size(); tri++)
                _current[tri]+=docOffset;
        }
    }

    void mergeInto(const char* path)
    {
    }
public:
    void    saveToDir(const char* dirPath) const;
    bool    loadFromDir(const char* dirPath);
public:
    void FindDocuments(const char* text, std::vector<size_t>* hitArray) const;
    size_t NbDocuments() const { return _docArray.size(); }
    const char* GetDocumentDir(size_t docId) const
    {
        return _dirArray[_docArray[docId].first].c_str();
    }
    const char* GetDocumentName(size_t docId) const
    {
        return _docArray[docId].second.c_str();
    }
    char* GetDocumentPath(size_t docId, char* path, size_t pathLen) const
    {
        const std::pair<size_t, std::string>& _pair = _docArray[docId];
        snprintf(path, pathLen, "%s%s",
                 _dirArray[_pair.first].c_str(), _pair.second.c_str());
        return path;
    }
};

/**
 * @brief The IndexBuilder class, designed to scan documents and fills triindex
 */
class IndexBuilder
{
protected:
    TriIndex* _index;
public:
    unsigned char triBits[64*64*64/8]; // 32768 kbytes
    size_t  enumerated, parsed, parsedBytes;
public:
    IndexBuilder():_index(NULL)
    {
        enumerated = 0;
        parsed = 0;
        parsedBytes = 0;
    }

    explicit IndexBuilder(TriIndex* indexToBuild):_index(indexToBuild)
    {
        enumerated = 0;
        parsed = 0;
        parsedBytes = 0;
    }
    void    clearTriBits() { memset(triBits, 0, sizeof(triBits)); }
    int     indexBuffer(const char* buffer);
    int     indexBuffer(const char* buffer, size_t len);
    int     indexFile(const char* path);
    void    indexDir(const char* dirPath);
public:
    static int _indexBuffer(const char* buffer, size_t bufferLen, unsigned char triBits[])
    {
        const char* ptr = buffer;
        const char* ptrEnd = bufferLen>0?buffer+bufferLen:NULL;
        int prevHash64 = -1;
        int nbtris = 0;
        int numLine = 0;
        int tris[3] = {0, 0, 0};
        for (;;)
        {
            char c = *ptr++;
            if (c == '\0')
                break;
            if ((ptrEnd != NULL)&&(ptr >= ptrEnd))
                break;

            // will hash c into a lower resolution (64bits) character
            int hash64 = 0;
            if (c == '\n')
                ++numLine;
            hash64 = TriIndex::_hash64(c);
            if (nbtris >= 2)
            {
                tris[2] = hash64;
                size_t i64 = (tris[0]<<12) + (tris[1]<<6) + tris[2]; // trigram computation
                triBits[i64>>3] |= 1<<(i64 & 7);
                tris[0] = tris[1];
                tris[1] = tris[2];
                tris[2] = 0;
                nbtris++;
            }
            else
            {
                tris[nbtris++] = hash64;
            }
            prevHash64 = hash64;
        }
        return nbtris;
    }

};

#ifdef USE_MT_BUILDER
// MT stands for multi-threaded index builder
#include "../timeutil.h"
#include "../processutil.h"

class MTIndexBuilder: public IndexBuilder
{
    int                         _indexerCount;
    std::vector<std::string>        _dirQueue;
    bool                            _dirQueueIsEmpty;
    putil::pthread_mutex_t          _queueMutex;
public:
    explicit MTIndexBuilder(TriIndex* indexToBuild, int indexerCount)
        :IndexBuilder(indexToBuild)
    {
        _indexerCount = indexerCount;
        putil::pthread_mutex_init(&_queueMutex, NULL);
    }
    bool reserveDirectory(char* buffer, size_t bufferSize)
    {
        bool res = true;
        putil::pthread_mutex_lock(&_queueMutex);
        if (_dirQueue.size()==0)
            res = false;
        else
        {
            strncpy(buffer, _dirQueue.back().c_str(), bufferSize);
            _dirQueue.pop_back();
            ++parsed;
            static int oldPercent = -1;
            int percent = (parsed*100)/enumerated;
            if (percent != oldPercent)
            {
                printf("%02d%% parsed (%d / %d)...\n", percent, parsed, enumerated);
                fflush(stdout);
                oldPercent = percent;
            }

        }
        _dirQueueIsEmpty = _dirQueue.size()==0;
        putil::pthread_mutex_unlock(&_queueMutex);
        return res;
    }
    int indexDir(const char* dirPath)
    {
        enumerated = parsed = parsedBytes = 0;
        //resetBuffers();
        indexManager.initialize();
        _indexDir(dirPath);
        enumerated = _dirQueue.size();
        parsed = 0;
        indexManager.addTask(new Indexer(this));
        indexManager.addTask(new Indexer(this));
        indexManager.addTask(new Indexer(this));
//       indexManager.startAll();

        while (!_dirQueueIsEmpty)
        {
            indexManager.manageTasks();
            putil::sleepMs(1000);
        }

        indexManager.shutdown(10000);
        printf("Indexing done !");
        return 0;
    }
protected:
    int _indexDir(const char *dirPath)
    {
        _finddata_t finddata;
        int findHandle;
        bool done;
        size_t directoryId = -1;
        {
            char mask[FILENAME_MAX];
            snprintf(mask, sizeof(mask), "%s*", dirPath);
            _dirQueue.push_back(dirPath);
            printf("queuing dir %s\n", mask);
            fflush(stdout);
            findHandle = _findfirst(mask , &finddata);
            done = findHandle == -1;
        }
        while (!done)
        {
            //printf("found %s\n", finddata.name);
            //fflush(stdout);
            if ((finddata.attrib & _A_SUBDIR) != 0)
            {
                bool badDir = (((finddata.name[0] == '.')&&(finddata.name[1] == '\0'))||
                               ((finddata.name[0] == '.')&&(finddata.name[1] == '.')&&(finddata.name[2]== '\0'))
                               );
                if (!badDir)
                {
                    char fullPath[FILENAME_MAX*2];
                    snprintf(fullPath, ARRAYSIZE(fullPath), "%s%s\\", dirPath, finddata.name);
                    _indexDir(fullPath);
                }
            }
            done = _findnext(findHandle, &finddata) == -1;
        }
        if (findHandle != -1)
            _findclose(findHandle);
        return 0;
    }
protected:
    TaskManager indexManager;
    class Indexer: public TaskHandler, IndexBuilder, TriIndex
    {
        MTIndexBuilder* _mtbuilder;
        size_t enumerated, parsed;
    public:
        Indexer(MTIndexBuilder* mtbuilder):_mtbuilder(mtbuilder), enumerated(0), parsed(0)
        {
            init();
        }
        // virtual
        int _indexDir(const char *dirPath)
        {
            _finddata_t finddata;
            int findHandle;
            bool done;
            {
                char mask[FILENAME_MAX];
                snprintf(mask, sizeof(mask), "%s/*", dirPath);
                findHandle = _findfirst(mask , &finddata);
                done = findHandle == -1;
            }
            size_t directoryId = -1;
            while (!done)
            {
                //printf("found %s\n", finddata.name);
                //fflush(stdout);
                if ((finddata.attrib & _A_SUBDIR) != 0)
                {
                }
                else
                {
                    ++enumerated;
                    clearTriBits();
                    char path[FILENAME_MAX*2];
                    snprintf(path, ARRAYSIZE(path), "%s%s", dirPath, finddata.name);
                    indexBuffer(path);
                    indexFile(path);
                    if (directoryId == -1)
                        directoryId = addDirectory(dirPath);
                    size_t docId = addDocument(directoryId, finddata.name);
                    insertTrigrams(docId, triBits);
                }
                done = _findnext(findHandle, &finddata) == -1;
            }
            if (findHandle != -1)
                _findclose(findHandle);
            return 0;
        }

        int Execute()
        {
            while (!TaskHandler::isStopping())
            {
                char path[MAX_PATH];
                if (_mtbuilder->reserveDirectory(path, ARRAYSIZE(path)))
                {
                    _indexDir(path);
                    //_mtbuilder->releaseDirectory(id);
                }
                else
                    putil::sleepMs(50);
            }
            return 0;
        }
    };
};
#endif  // USE_MTHREAD_INDEX

#ifdef WANT_TRIINDEX_IMPLEM
const char TriIndex::_validChars[64]=
        "abcdefghijklmnopqrstuvwxyz"
        "0123456789"
        "#/*-+=&/!_()[]{}<>\"'.,:$%";
// Set trigrams bit array to 1 for each trigram present

/**
 * @brief TriIndex::FindDocuments
 * @param text
 * @param hitArray
 */
void TriIndex::FindDocuments(const char* text, std::vector<size_t>* hitArray) const
{
    const char*ptr = text;
    const char*ptrEnd = NULL;
    int nbtris = 0;
    int tris[3] = {0, 0, 0};
    int prevHash64 = -1;
    int iteration = 0;
    for (;;)
    {
        char c = *ptr++;
        if (c == '\0')
            break;
        if ((ptrEnd != NULL)&&(ptr >= ptrEnd))
            break;

        // will hash c into a lower resolution character
        int hash64 = _hash64(c);
        if (nbtris >= 2)
        {
            tris[2] = hash64;
            // will change a triplet of character into a lower resolution index
            int index = (tris[0]<<12)+(tris[1]<<6)+tris[2];
            // we're doing ANDs between lists of documents: if one is empty, everything is.
            // list size is at most size of the smallest lists
            if (_masterTrigrams[index].size() == 0)
            {
                hitArray->clear();
                return;
            }            
            if (hitArray->size() == 0)  // first time, copy the whole list
            {
                hitArray->assign(_masterTrigrams[index].begin(), _masterTrigrams[index].end());
            }
            else
            {
                // we're merging another list with the current one: it always result in a smaller list
                // so, to gain time, we're overwriting the current list without erasing(): as it takes
                // TOO MUCH time
                int currentIndex = 0, otherIndex = 0;
                const uint32_array& other = _masterTrigrams[index];
                int newCount = 0;
                while (currentIndex < (int)hitArray->size())
                {
                    size_t docId = (*hitArray)[currentIndex++];
                    bool found = false;
                    while ((otherIndex < (int)other.size())&&(other[otherIndex] < docId))
                    {
                        otherIndex++;
                        iteration++;
                    }
                    if (otherIndex >= other.size())
                    {
                        // we didnt found the document, and we finished parsing the other list
                        break;
                        //hitArray->erase(hitArray->begin()+i, hitArray->end());
                        //break;
                    }
                    if (other[otherIndex] != docId)
                    {
                        continue;
                        //hitArray->erase(hitArray->begin()+i);
                        //continue;
                    }
                    (*hitArray)[newCount++] = docId;
                }
                hitArray->resize(newCount);
                if (newCount == 0)
                    return;
            }
            tris[0] = tris[1];  // rolling key
            tris[1] = tris[2];
            tris[2] = 0;
            nbtris++;
        }
        else
        {
            tris[nbtris++] = hash64;
        }
        prevHash64 = hash64;
    }
    printf("%d docs iterated, %d lists combined\n", iteration, nbtris-2);
    fflush(stdout);
}

int IndexBuilder::indexBuffer(const char* buffer)
{
    return indexBuffer(buffer, 0);
}

inline int IndexBuilder::indexBuffer(const char* buffer, size_t bufferLen)
{
    return _indexBuffer(buffer, bufferLen, triBits);
}

int IndexBuilder::indexFile(const char* path)
{
    FILE* fi = fopen(path, "rt");
    if (fi == NULL)
        return -1;
    int nbTrigs = 0;
    char buffer[1024];
    //
    while (fgets(buffer, 1024, fi)!=NULL)
    {
        nbTrigs += indexBuffer(buffer);
    }
    /*
    for (;;) {
        size_t _read = fread(buffer, 1, 1024, fi);
        if (_read>0)
            nbTrigs += indexBuffer(buffer, _read);
        if (_read!=1024)
            break;
    }*/
    fclose(fi);

    return nbTrigs;
}
/**
 * @brief IndexBuilder::indexDir
 * @param path of a directory, has to end with a trailing dir separator (if necessary)
 */
void IndexBuilder::indexDir(const char* path)
{
    _finddata_t finddata;
    int findHandle;
    bool done;
    size_t directoryId = -1;
    {
        char mask[FILENAME_MAX];
        snprintf(mask, sizeof(mask), "%s*", path);
        printf("indexing %s\n", mask);
        fflush(stdout);
        findHandle = _findfirst(mask , &finddata);
        done = findHandle == -1;
    }
    while (!done)
    {
        //printf("found %s\n", finddata.name);
        //fflush(stdout);
        if ((finddata.attrib & _A_SUBDIR) != 0)
        {
            bool badDir = (((finddata.name[0] == '.')&&(finddata.name[1] == '\0'))||
                           ((finddata.name[0] == '.')&&(finddata.name[1] == '.')&&(finddata.name[2]== '\0')) );
            if (!badDir)
            {
                char fullPath[MAX_PATH];
                snprintf(fullPath, ARRAYSIZE(fullPath), "%s%s\\", path, finddata.name);
                indexDir(fullPath);
            }
        }
        else
        {
            // retrieve trigrams from document
            char fullPath[MAX_PATH];
            snprintf(fullPath, ARRAYSIZE(fullPath), "%s%s", path, finddata.name);

            clearTriBits();
            indexBuffer(fullPath);
            indexFile(fullPath);

            if (directoryId == (size_t)-1)
                directoryId = _index->addDirectory(path);
            ++enumerated;
            ++parsed;
            parsedBytes += finddata.size;

            size_t docId = _index->addDocument(directoryId, finddata.name);
            _index->insertTrigrams(docId, triBits);
        }
        done = _findnext(findHandle, &finddata) == -1;
    }
    if (findHandle != -1)
        _findclose(findHandle);
}

void TriIndex::shutdown()
{
    printf("... clearing doc array\n");
    fflush(stdout);
    _dirArray.clear();
    _docArray.clear();
    printf("... clearing trigrams\n");
    fflush(stdout);
    for (int i=0; i<_masterTrigrams.size(); i++)
    {
        _masterTrigrams[i].clear();    
    }
    _masterTrigrams.clear();
    //printf("index shutdown\n");
    //fflush(stdout);
}

void TriIndex::init()
{
    _masterTrigrams.resize(64*64*64);
    memset(_masterTrigrams.begin(), 0, _masterTrigrams.allocated());
}

/**
 * @brief TriIndex::saveToDir
 * @param dirPath will save three files in it cs_dirs, cs_docs and cs_trigrams
 */
void TriIndex::saveToDir(const char* dirPath) const
{
    char path[MAX_PATH];

    snprintf(path, sizeof(path), "%s\\cs_dirs.dat", dirPath);
    FILE* fi = fopen(path, "wb");
    uint32_t value32 = _dirArray.size();
    fwrite(&value32, sizeof(value32), 1, fi);
    for (int i=0; i<(int)_dirArray.size(); i++)
    {
        uint16_t value16 = _dirArray[i].length();
        fwrite(&value16, sizeof(value16), 1, fi);
        fwrite(_dirArray[i].c_str(), value16, 1, fi);
    }
    fclose(fi);

    snprintf(path, sizeof(path), "%s\\cs_docs.dat", dirPath);
    fi = fopen(path, "wb");
    value32 = _docArray.size();
    fwrite(&value32, sizeof(value32), 1, fi);
    for (int i=0; i<(int)_docArray.size(); i++)
    {
        value32 = _docArray[i].first;
        fwrite(&value32, sizeof(value32), 1, fi);
        short value16 = _docArray[i].second.length();
        fwrite(&value16, sizeof(value16), 1, fi);
        fwrite(_docArray[i].second.c_str(), value16, 1, fi);
    }

    //
    snprintf(path, sizeof(path), "%s\\cs_trigrams.dat", dirPath);
    fi = fopen(path, "wb");
    for (int i = 0; i<64*64*64; i++)
    {
        value32 = _masterTrigrams[i].size();
        fwrite(&value32, sizeof(value32), 1, fi);
    }
    for (int i=0; i<64*64*64; i++) {
        fwrite(_masterTrigrams[i].begin(), sizeof(uint32_t), _masterTrigrams[i].size(), fi);
    }

    fclose(fi);

}

bool TriIndex::loadFromDir(const char* dirPath)
{
    uint32_t count32;
    uint32_t value32;
    uint16_t value16;

    char path[260];
    snprintf(path, sizeof(path), "%s\\cs_dirs.dat", dirPath);
    FILE* fi = fopen(path, "rb");
    if (fi == NULL)
        return false;
    init();
    fread(&count32, sizeof(count32), 1, fi);
    _dirArray.resize(count32);
    for (uint32_t i=0; i<count32; i++)
    {
        uint16_t value16;
        fread(&value16, sizeof(value16), 1, fi);
        fread(path, value16, 1, fi);
        path[value16] = 0;
        _dirArray[i].assign(path);
    }
    fclose(fi);
    //
    snprintf(path, sizeof(path), "%s\\cs_docs.dat", dirPath);
    fi = fopen(path, "rb");
    fread(&count32, sizeof(count32), 1, fi);
    for (uint32_t i=0; i<count32; i++)
    {
        fread(&value32, sizeof(value32), 1, fi);
        fread(&value16, sizeof(value16), 1, fi);
        fread(path, value16, 1, fi);
        path[value16] = 0;
        _docArray.push_back(std::pair<uint32_t, std::string>(value32, std::string(path)));
    }
    fclose(fi);
    //
    snprintf(path, sizeof(path), "%s\\cs_trigrams.dat", dirPath);
    fi = fopen(path, "rb");
    for (int i = 0; i<64*64*64; i++)
    {
        fread(&value32, sizeof(value32), 1, fi);
        _masterTrigrams[i].resize(value32);
    }
    for (int i=0; i<64*64*64; i++) {
        fread(_masterTrigrams[i].begin(), sizeof(uint32_t), _masterTrigrams[i].size(), fi);
    }
    fclose(fi);
    return true;
}
#endif

#endif  // INDEX_TRIINDEX_H_
